package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2022-01-03 10:09
 * @description: Functions of this class is
 **/
public class 动态规划礼物的最大价值 {
    public int maxValue(int[][] grid) {
        //初看感觉就是机器人走格子的改版，很模板的题目，动态规划嘛
        int len1=grid.length;
        int len2=grid[0].length;
        int dp[][]=new int[len1][len2];
        dp[0][0]=grid[0][0];
        for(int i=1;i<len1;i++){
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int j=1;j<len2;j++){
            dp[0][j]=dp[0][j-1]+grid[0][j];
        }
        for(int i=1;i<len1;i++){
            for(int j=1;j<len2;j++){
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[len1-1][len2-1];
    }
}